package 排序;
import java.util.Arrays;
/**
 * Created by Administrator on 2017/8/25.
 */
//1、堆节点的访问
//通常堆是通过一维数组来实现的。在数组起始位置为0的情形中：
//  父节点i的左子节点在位置(2*i+1);
//  父节点i的右子节点在位置(2*i+2);
//  子节点i的父节点在位置floor((i-1)/2);

//2、堆的操作
//在大根堆的数据结构中，堆中的最大值总是位于根节点(在优先队列中使用堆的话堆中的最小值位于根节点)。堆中定义以下几种操作：
//  最大堆调整（Max_Heapify）：将堆的末端子节点作调整，使得子节点永远小于父节点
//  创建最大堆（Build_Max_Heap）：将堆所有数据重新排序
//  堆排序（HeapSort）：移除位在第一个数据的根节点，并做最大堆调整的递归运算

//这是小根堆排序(最小值在树根处---即数组最小索引处)
public class HeapSort {

    private int[] arr;

    public HeapSort(int[] arr){
        this.arr = arr;
    }

    /**
     * 堆排序的主要入口方法，共两步。
     */
    public void sort(){
        /*
         *  第一步：将数组堆化(每次只是考虑一个父节点+两个子节点的小堆，最终堆化后，只有堆顶元素为最大--满足大根堆定义)
         *  beginIndex = 第一个非叶子节点。
         *  从第一个非叶子节点开始即可。无需从最后一个叶子节点开始。
         *  ---叶子节点可以看作已符合堆要求的节点，根节点就是它自己且自己以下值为最大。
         */
        int len = arr.length - 1;  //数组最大索引
        int beginIndex = (len - 1) >> 1; //数组最大索引处节点的父节点索引(即第一个非叶子节点)
        for(int i = beginIndex; i >= 0; i--){ //从第一个非叶子节点向堆定搜索，依次建立最大堆
            maxHeapify(i, len); //进行最大堆整理(父节点值>=子节点值)
        }

        /*
         * 第二步：对堆化数据排序(小根堆排序---最小值在树根处)
         * 每次都是移出最顶层的根节点A[0]，与最尾部节点位置调换，同时遍历长度 - 1。
         * 然后重新整理被换到根节点的末尾元素，使其符合堆的特性。
         * 直至未排序的堆长度为 0。
         */
        for(int i = len; i > 0; i--){
            swap(0, i);
            maxHeapify(0, i - 1);
        }
    }

    private void swap(int i,int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    /**
     * 调整索引为 index 处的数据，使其符合大根堆的特性(父节点的值>=左右子节点的值)。
     *
     * @param index 需要堆化处理的数据的索引
     * @param len 未排序的堆（数组）的长度--最大索引
     */
    private void maxHeapify(int index,int len){
        int left = (index << 1) + 1; // 左子节点索引
        int right = left + 1;           // 右子节点索引

        int cMax = left;             // 子节点值最大索引，默认左子节点。

        if(left > len) return;       // 左子节点索引超出计算范围，直接返回。
        if(right <= len && arr[right] > arr[left]) // 先判断右子节点没有越界，再比较左右子节点哪个较大。
            cMax = right;

        if(arr[cMax] > arr[index]){
            swap(cMax, index);      // 如果父节点被子节点调换，
            maxHeapify(cMax, len);  // 则需要继续判断换下后的父节点，是否符合新堆的特性(递归判断其子堆是否满足大根堆特性，不满足调整)。
             //形象解释：即将临时领导和其左右臂中能力较强者互换位置后，还需要考验原本的临时领导是否能胜任 其被提拔的人的位置。
        }
    }

    /**
     * 测试用例
     *
     * 输出：
     * [0, 0, 0, 1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 7, 7, 7, 8, 8, 8, 9, 9, 9]
     */
    public static void main(String[] args) {
        int[] arr = new int[]{3,5,3,0,8,6,1,5,8,6,2,4,9,4,7,0,1,8,9,7,3,1,2,5,9,7,4,0,2};
        new HeapSort(arr).sort();
        System.out.println(Arrays.toString(arr));
    }

}
